/*******************************************************************
 *  EP 1 - MAC2301 - 1º Semestre/2011                              *
 *                                                                 *
 *  João Victor Henna Sallaberry                                   *
 *  6913166                                                        *
 *******************************************************************/

#include <stdio.h>
#include <stdlib.h>

#include "ep1.h"

#include "GUI/backend-publico.h"
#include "resolver.h"
#include "aux.h"
#include "pilha.h"

/* Esta função resolve o sudoku */
void resolveSudoku (){
	int linha, coluna, i, j, k, jogadas, x, y, var, quebrou, falhou;
	Sudoku sudoku, sudoku_desempilhado;
	Pilha pilha;

	limpa(&pilha);

	preencheCertezas();
	printStatus();
	jogadas=1;
	quebrou=0;
	sudoku_desempilhado.valor_do_chute=0;
	linha=1;
	coluna=1;
	k=1;


	while(ganhou()==FALHA){
		while(jogadas==1){
			for(; linha<=9; linha++){
				if(coluna>=10)
					coluna=1;
				for(; coluna<=9; coluna++){
					if(pegaNumero(linha,coluna)==0){
						/*chuta valor*/
						for(; k<=9; k++)
							if(verificaSePodeColocarNumero(k,linha,coluna)==SUCESSO){
								/*empilha estado atual no sudoku*/
								sudoku.valor_do_chute=k;
								sudoku.casa_do_chute=(9*(linha-1)+(coluna-1));
								for(i=1; i<=9; i++)
									for(j=1; j<=9; j++)
										sudoku.jogo[9*(i-1)+(j-1)]=pegaNumero(i,j);
								empilha(sudoku, &pilha);
								setaNumero(linha,coluna,k);
								break;
							}
						if(k>=10)
							jogadas=0;
						preencheCertezas();
						printStatus();
						quebrou=1;
						break;
					}
				}
				if(quebrou==1){
					quebrou=0;
					break;
				}
			}
			/*ve se ainda há jogadas*/
			for(i=1; i<=9; i++)
				for(j=1; j<=9; j++)
					if(pegaNumero(i,j)==0){
						falhou=0;
						for(var=1; var<=9;var++){
							if(verificaSePodeColocarNumero(var,i,j)==FALHA)
								falhou++;
							if(falhou==9)
								jogadas=0;
						}
					}
			if(ganhou()==SUCESSO)
				jogadas=0;
			if(jogadas==1)
				k=1;

		}

		if(ganhou()==FALHA){
			/*desempilha*/
			desempilha(&sudoku_desempilhado,&pilha);
			/*volta sudoku ao estado anterior*/
			for(i=1; i<=9; i++)
				for(j=1; j<=9; j++)
					setaNumero(i,j,sudoku_desempilhado.jogo[9*(i-1)+(j-1)]);
			if(k>=10){
				linha=(sudoku_desempilhado.casa_do_chute/9)+1;
				coluna=(sudoku_desempilhado.casa_do_chute%9)+1;
			}
			k=sudoku_desempilhado.valor_do_chute+1;

			jogadas=1;

			while(k>=9){
				/*desempilha*/
				desempilha(&sudoku_desempilhado,&pilha);
				/*volta sudoku ao estado anterior*/
				for(i=1; i<=9; i++)
					for(j=1; j<=9; j++)
						setaNumero(i,j,sudoku_desempilhado.jogo[9*(i-1)+(j-1)]);
				if(k>=10){
								linha=(sudoku_desempilhado.casa_do_chute/9)+1;
								coluna=(sudoku_desempilhado.casa_do_chute%9)+1;
							}
				k=sudoku_desempilhado.valor_do_chute+1;
			}
		}
	}

}

/* Esta função retorna SUCESSO caso o jogo esteja resolvido. FALHA caso contrário */
int ganhou (){
	int i, j, k, linha, coluna, numero;

	for(linha=1; linha<=9; linha++)
		for(coluna=1; coluna<=9; coluna++){
			numero=pegaNumero(linha, coluna);
			if(numero==0)
				return FALHA;

			/* checa proibições na linha */
			for(k=1; k<=9; k++){
				if(k!=coluna && numero==pegaNumero(linha, k))
					return FALHA;
			}
			/* checa proibições na coluna */
			for(k=1; k<=9; k++){
				if(k!=linha && numero==pegaNumero(k, coluna))
					return FALHA;
			}
			/* checa proibições no bloco */
			if(linha<=3 && coluna<=3)
				for(i=1; i<=3; i++)
					for(j=1; j<=3; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
			if(linha<=3 && coluna>=4 && coluna<=6)
				for(i=1; i<=3; i++)
					for(j=4; j<=6; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
			if(linha<=3 && coluna>=7)
				for(i=1; i<=3; i++)
					for(j=7; j<=9; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
			if(linha>=4 && linha<=6 && coluna<=3)
				for(i=4; i<=6; i++)
					for(j=1; j<=3; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
			if(linha>=4 && linha<=6 && coluna>=4 && coluna<=6)
				for(i=4; i<=6; i++)
					for(j=4; j<=6; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
			if(linha>=4 && linha<=6 && coluna>=7)
				for(i=4; i<=6; i++)
					for(j=7; j<=9; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
			if(linha>=7 && coluna<=3)
				for(i=7; i<=9; i++)
					for(j=1; j<=3; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
			if(linha>=7 && coluna>=4 && coluna<=6)
				for(i=7; i<=9; i++)
					for(j=4; j<=6; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
			if(linha>=7 && coluna>=7)
				for(i=7; i<=9; i++)
					for(j=7; j<=9; j++){
						if(i!=linha || j!=coluna)
							if(numero==pegaNumero(i, j))
								return FALHA;
					}
		}

	return SUCESSO;
}

/* Esta função verifica se o número "numero" pode ser colocado na linha "linha" e na coluna "coluna".
 * Retorna SUCESSO caso seja possível, FALHA caso contrário. */
int verificaSePodeColocarNumero(int numero, int linha, int coluna){
	int i, j, k;

	if(fixo(linha,coluna)==1)
		return FALHA;

	/* checa proibições na linha */
	for(k=1; k<=9; k++){
		if(numero==pegaNumero(linha, k))
			return FALHA;
	}
	/* checa proibições na coluna */
	for(k=1; k<=9; k++){
		if(numero==pegaNumero(k, coluna))
			return FALHA;
	}
	/* checa proibições no bloco */
	if(linha<=3 && coluna<=3)
		for(i=1; i<=3; i++)
			for(j=1; j<=3; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}
	if(linha<=3 && coluna>=4 && coluna<=6)
		for(i=1; i<=3; i++)
			for(j=4; j<=6; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}
	if(linha<=3 && coluna>=7)
		for(i=1; i<=3; i++)
			for(j=7; j<=9; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}
	if(linha>=4 && linha<=6 && coluna<=3)
		for(i=4; i<=6; i++)
			for(j=1; j<=3; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}
	if(linha>=4 && linha<=6 && coluna>=4 && coluna<=6)
		for(i=4; i<=6; i++)
			for(j=4; j<=6; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}
	if(linha>=4 && linha<=6 && coluna>=7)
		for(i=4; i<=6; i++)
			for(j=7; j<=9; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}
	if(linha>=7 && coluna<=3)
		for(i=7; i<=9; i++)
			for(j=1; j<=3; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}
	if(linha>=7 && coluna>=4 && coluna<=6)
		for(i=7; i<=9; i++)
			for(j=4; j<=6; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}
	if(linha>=7 && coluna>=7)
		for(i=7; i<=9; i++)
			for(j=7; j<=9; j++){
				if(numero==pegaNumero(i, j))
					return FALHA;
			}

	return SUCESSO;
}



